// 84.柱状图中的最大矩形
package LeetcodeHot100;

import java.util.Deque;
import java.util.LinkedList;

public class Solution084 {
    public int largestRectangleArea(int[] heights) {
        int result = 0;

        // 在 heights 的前后加上0
        int[] Heights = new int[heights.length + 2];
        Heights[0] = 0;
        Heights[heights.length + 1] = 0;
        System.arraycopy(heights, 0, Heights, 1, heights.length);

        // 单调栈，存储index
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        // 当栈不再单调，则出栈并进行计算
        for (int i = 1; i < Heights.length; i++) {
            while (Heights[i] < Heights[stack.peek()]) {
                int height = Heights[stack.pop()];
                result = Math.max(result, height * (i - stack.peek() - 1));
            }
            stack.push(i);
        }
        // 此时栈里面应该还剩0元素
        return result;
    }
}